/**
题目:
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    string multiply(string num1, string num2) {
        if( num1.size() == 0 || num2.size() == 0) return "0";
        vector<int> iv(num1.size()+num2.size(),0);
        for(int i = num1.size()-1;i > -1;i--)
        {
            for( int j = num2.size()-1;j > -1;j--)
            {
                int val = (num1[i] - '0')*(num2[j] - '0');
                int sum = val+iv[i+j+1];
                iv[i+j+1] = sum % 10;
                iv[i+j] += sum/10;//高位不用考虑进位，可用保存2位数
                                 // 下一轮计算会处理该位置的进位
                                 // 末一轮也不影响，因为是最高位，直接转字符串结果一样
            }
        }
        while(iv.size() > 1 && iv[0] == 0)
            iv.erase(iv.begin());
        string res;
        for(int i = 0;i < iv.size();i++)
        {
            res.push_back('0'+iv[i]);
        }
        return res;
    }
};
 